package leet.explore;

import java.util.*;

/**
 * @author fance
 * @date 18-6-29 上午5:05
 */
public class Third {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length < 1) {
            return res;
        }
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            spiralOrderCore(matrix,tR++,tC++,dR--,dC--,res);
        }
        return res;
    }
    private void spiralOrderCore(int [][] matrix, int tR, int tC, int dR, int dC,List<Integer> res) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                res.add(matrix[tR][i]);
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                res.add(matrix[i][tC]);
            }
        } else {
            int curC = tC;
            int curR = tR;
            while (curC != dC) {
                res.add(matrix[tR][curC]);
                curC++;
            }
            while (curR != dR) {
                res.add(matrix[curR][curC]);
                curR++;
            }
            while (curC != tC) {
                res.add(matrix[curR][curC]);
                curC--;
            }
            while (curR != tR) {
                res.add(matrix[curR][curC]);
                curR--;
            }
        }
    }

    // 1.sort 2.容器on on  3.链表环路口法,难以理解.
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int n : nums) {
            if (set.contains(n)) {
                return n;
            }
            set.add(n);
        }
        return -1;
    }
    // 1.bf 2. sort 3.set 感觉相当与暴力
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;
        for (int num : num_set) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> ret = maxSlidingWindowCore(nums,k);
        int[] res = new int[ret.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = ret.get(i);
        }
        return res;
    }
    public List<Integer> maxSlidingWindowCore(int[] nums, int k) {
        List<Integer> ret = new ArrayList<>();
        int len = nums.length;
        if (nums == null || k <= 0 || k > len) {
            return ret;
        }
        for (int i = 0; i < len - k + 1; i++) {
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int j = i; j < k + i; j++) {
                tmp.add(nums[j]);
            }
            Collections.sort(tmp);
            ret.add(tmp.get(tmp.size() - 1));
        }
        return ret;
    }


}
